package code;

import java.util.HashMap;
import java.util.Map;

public class Code76 {
	
	/*
	 * 先从0开始找到能覆盖T的S[0...j],之后，再移动左端点i,一个
	 */
    public String minWindow(String s, String t) {
        int i,j;
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        for(i=0;i<t.length();i++){
        	char c=t.charAt(i);
        	if(map.containsKey(c)){
        		map.put(c, map.get(c)+1);
        	}
        	else
        		map.put(c, 1);
        }
        if(t.length()==0 || s.length()<t.length())
        	return "";
        int minLen=s.length()+1;
        String result="";
        Map<Character,Integer> record=new HashMap<Character,Integer>();
        Map<Character,Integer> copyMap=new HashMap<Character,Integer>(map);
        /*
         * 先S[0..j]找到能覆盖T的j
         */
    	for(i=0;i<s.length();i++){
    		char c=s.charAt(i);
    		if(!map.containsKey(c))
    			continue;
    		if(record.containsKey(c)){
    			record.put(c, record.get(c)+1);
    		}
    		else
    			record.put(c, 1);
    		if(copyMap.containsKey(c)){
    			int x=copyMap.get(c);
    			if(x==1){
    				copyMap.remove(c);
    				if(copyMap.isEmpty()){
        				break;
    				}
    			}
    			else{
    				copyMap.put(c, x-1);
    			}
    		}
        }
    	if(i==s.length()){
    		return "";
    	}
    	j=i;
    	minLen=i+1;
    	result=s.substring(0, j+1);
    	/*
    	 * 移动左边的指针i，记录下来，找右边第一个s[j]的替代S[i]
    	 */
    	for(i=0;i<s.length()-t.length() && j<s.length();i++){
    		char c=s.charAt(i);
    		System.out.println(i+" "+j);
    		if(!map.containsKey(c)){
    			//t中没有c，忽略此字符
    			if(j-i<minLen){
    				minLen=j-i;
    				
    				result=s.substring(i+1, j+1);
    			}
    		}
    		else{//t包含c
        		/*
        		 * 在record中删掉1个c
        		 */
        		record.put(c, record.get(c)-1);
    			if(record.get(c)>=map.get(c)){
    				//依然还是能包含t
    	  			if(j-i<minLen){
        				minLen=j-i;
        				result=s.substring(i+1, j+1);
        			}
    			}
    			else{
    				//往j之后找替代c
    				do{
    					j++;
    					if(j==s.length())
    						break;
    					if(record.containsKey(s.charAt(j)))
    					{
    						record.put(s.charAt(j), record.get(s.charAt(j))+1);
    					}
    				}while(c!=s.charAt(j));
    				if(j==s.length())//找不到了下一个c了
    					break;
        			if(j-i<minLen){
        				minLen=j-i;
        				result=s.substring(i+1, j+1);
        			}
    			}
    		}
    	}
        return result;
    }
    public static void main(String[] args){
    	String s="cabwefgewcwaefgcf";
    	String t="cae";
    	System.out.println(new Code76().minWindow(s, t));
    }
}
